package com.agile.leetcode.array.calculate;

import java.util.*;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * @Author ChenZhangKun
 * @Date 2020/5/25 13:27
 */

/**
 * 给定一个整数数组 nums ，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。
 *
 * 示例 1：
 *
 *     输入：nums = [2,3,3,2,3,3]
 *
 *     输出：2
 *
 *     解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。
 *
 * 示例 2：
 *
 *     输入：nums = [2,3,5,7]
 *
 *     输出：4
 *
 *     解释：只有一种可行的切割：[2], [3], [5], [7]
 *
 * 限制：
 *
 *     1 <= nums.com.agile.leetcode.array.length <= 10^5
 *     2 <= nums[i] <= 10^6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/qie-fen-shu-zu
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@SuppressWarnings("all")
public class MaxYueShu {
    public static void main(String[] args) {
        Integer[] num={2,3,3,2,3,3};
        List<Integer[]> allSubArray = getAllSubArray(num);
        int sum = getSum(allSubArray);
        System.out.println(sum);
    }
    // 得到所有的子数组
    public static List<Integer[]> getAllSubArray(Integer[] array){
        int length = array.length;
        List<Integer[]> list = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if (i == length - 1) {
                list.add(new Integer[]{array[length - 1]});
                continue;
            }
            list.add(new Integer[]{array[i]});
            if (i == 0) {
                for (int j = i + 1; j < length; j++) {
                    Integer[] integers = new Integer[j + 1];
                    for (int m = i; m < j + 1; m++) {
                        integers[m] = array[m];
                    }
                    list.add(integers);
                }
            }
            else if (i == 1) {
                for (int j = i + 1; j < length; j++) {
                    Integer[] integers = new Integer[j];
                    int n = 0;
                    for (int m = i; m < j + 1; m++) {
                        integers[n] = array[m];
                        n++;
                    }
                    list.add(integers);
                }
            } else {
                int k=2;
                for (int j = i + 1; j < length; j++) {
                    Integer[] integers = new Integer[k];
                    int n = 0;
                    for (int m = i; m < j+1 ; m++) {
                        integers[n] = array[m];
                        n++;
                    }
                    list.add(integers);
                    k++;
                }
            }
        }
        return list;
    }
    // 去除公约数小于一的
    public static int getSum(List<Integer[]> list){
        Predicate<Integer[]> p1=o1->{
            int max = getMax(o1[0], o1[o1.length - 1]);
            if (max>1){
                System.out.println(Arrays.toString(o1));
                return true;
            }else {
                return false;
            }
        };
        List<Integer[]> collect = list.stream().filter(p1).collect(Collectors.toList());
        List<Integer[]> repeateArray=new ArrayList<>();
        // 去重
        int size = collect.size();
        for (int i = 0; i <size-1 ; i++) {
            for (int j = i+1; j < size; j++) {
                if (Arrays.equals(collect.get(i),collect.get(j))){
                    repeateArray.add(collect.get(j));
                }
            }
        }
        for (Integer[] integers : repeateArray) {
            collect.remove(integers);
        }
        //Set<>
        return collect.size();
    }
    // 求最大公约数
    public static int getMax(int a,int b){
        if (a%b==0){
            return b;
        }else {
            return getMax(b,a%b);
        }

    }
}
class test {
    public static void main(String[] args) {
        int[] integers = {1, 2};
        int[] integers1 = {1, 2};
        System.out.println(integers == integers1);
        System.out.println(integers.equals(integers1));
        System.out.println(Arrays.equals(integers, integers1));
    }
}
class Leetcode{
    private List<Integer> prim;
    private int Pn = 1000050;
    private boolean[] isnotprime = new boolean[Pn];
    private int[] pflag = new int[Pn];

    private void sovleP()
    {
        Arrays.fill(isnotprime,false);
        isnotprime[0] = true;
        isnotprime[1] = true;

        prim = new ArrayList<>();

        for (int i = 2; i * i < Pn ; i++)
        {
            if(isnotprime[i]) continue;
            prim.add(i);
            for (int j = i; j < Pn; j += i)
            {
                isnotprime[j] = true;
            }
        }
    }

    public int splitArray(int[] nums)
    {
        int ans = 0;
        if(nums == null || nums.length == 0) return ans;

        // 求解所有素数
        sovleP();

        int n = nums.length;
        int[] dp = new int[n+1];

        List<Integer> has = new ArrayList<>();
        Arrays.fill(pflag,n);// 所有的质数最小划分数都是n
        Arrays.fill(dp,n);

        dp[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            // 得到当前值
            int x = nums[i-1];
            has.clear();// 有哪些素数

            for (int j = 0; j < prim.size(); j++)
            {
                int p = prim.get(j);
                if(x < p) break; // 比素数都要小，那肯定就出来了
                // 如果包含这个素数
                if(x % p == 0)
                {
                    has.add(p);
                    while (x % p == 0) x/=p; // 去掉所有素数
                }
            }

            // 还有余
            if(x != 1) has.add(x);

            // 先更新每个质数空间
            for (int j = 0; j < has.size(); j++)
            {
                int p = has.get(j);
                pflag[p] = Math.min(pflag[p],dp[i-1]);
            }

            for (int j = 0; j < has.size(); j++)
            {
                int p = has.get(j);
                dp[i] = Math.min(dp[i],pflag[p] + 1);
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        int i = new Leetcode().splitArray(new int[]{2, 3, 3, 2, 3, 3});
        System.out.println(i);
    }
}
